1. Field of the Invention
This invention relates generally to wireless communications methods and systems and, more specifically, to a Technique for Efficient Message Delivery in Ad Hoc, Mesh, Wireless Computer Networks.
2. Description of Related Art
Modern computer networks facilitate data transmission between multiple devices. Each device in the network receives every data transmission and then retransmits if the data is not intended for it. This ensures that the message will reach its intended recipient if possible. To prevent potential infinite message transmission loops, current computer networks employ a variety of tactics to make sure that data transactions ultimately expire (instead of being re-transmitted into perpetuity). One popular method is to use a “hop count” to determine the maximum number of nodes that the message can be relayed through. Under the conventional “hop count” approach, each transmission carries with it a TTL field that is decremented by each node it encounters. When the TTL field is zero, the message is no longer retransmitted (i.e. the message expires).
The “hop count” approach is adequate for linear or tree topologies, where the route has a natural endpoint, but it is very inefficient for mesh networks because for large hop counts the message will continue to be echoed throughout the network long after the message has been received by its intended recipient.
A second method commonly employed to prevent circular message loops is the “route table” approach., which can be accomplished in one of two ways. First, a central master device can keep a list of possible routes to each destination. In a second version, the network is pre-staged or initialized so that each node is expected to know its closest neighbor nodes.
Both “route table” methods are poor choices for ad hoc networks where devices can come and go or move around as they please. If a vital link in the network leaves the network (as is common in ad hoc, mesh topologies), then the route table is no longer valid and messages will not receive their intended recipient.
Current standard lower level networking protocols and techniques perform well in situations where the topology is tightly controlled or a central master server has complete control and knowledge of routing. However, these techniques fail or are wasteful when faced with network that both (1) have no set topology (mesh) and (2) allow devices to come and go as they please. Rings in the topology can create message loopbacks that propagate the message far after it's been received and missing critical path nodes can prevent messages from reaching their destination in systems where the route is known a priori. A modern transaction routing technique should be able to accommodate dynamic network devices and random topologies.
What is needed is a method to efficiently route messages in an ad hoc, mesh network that (1) ensures delivery of the message while (2) preventing recurring route loops. The method and system of the present invention puts forth such a method.
This invention seeks to provide a transaction routing technique that will enable modern wireless, ad hoc, mesh networks to meet these requirements. Broadcast messages ensure that every node in the network, regardless of the topology, receives the message while each node's message cache table permits the message to be transmitted only once through the system. Furthermore, because the message is not stored permanently at each node in the mesh network, the entire invention lends itself to low resource implementations.